package com.algorithmic.find;

import java.util.List;

/**
 * @author: zhangxupeng
 * @date:2019/6/27
 * @Email: 1452806452@qq.com
 **/
public class BinarySearch {
    /**
     * 二分查找算法
     *
     * @param list list 必须是有序的
     * @param toFind 需要查找的数
     * @return -1 没找到
     */
    public static int find(List<Integer> list,int toFind){

//        return commonFind(list,toFind);
        return recFind(list,toFind,0,list.size()-1);
    }

    /**
     * 普通的二分查找
     * @param list list 必须是有序的
     * @param toFind 需要查找的数
     * @return -1 没找到
     */
    public static int commonFind(List<Integer> list, int toFind) {
        int size = list.size();
        int lowerBound = 0;
        int upperBound = size - 1;
        int curIn;
        while (true) {
            curIn = (lowerBound + upperBound) / 2;
            if (toFind == list.get(curIn)) {
                return curIn;
            } else if (lowerBound > upperBound) {
                return -1;
            } else {
                if (list.get(curIn) < toFind) {
                    lowerBound = curIn + 1;
                } else {
                    upperBound = curIn - 1;
                }
            }
        }
    }

    /**
     * 递归二分查找
     * @param list list 必须是有序的
     * @param toFind 需要查找的数
     * @param lowerBound
     * @param upperBound
     * @return -1没找到
     */
    public static int recFind(List<Integer> list,int toFind,int lowerBound,int upperBound){
        int curIn = (lowerBound+upperBound)/2;
        if (list.get(curIn)==toFind){
            return curIn;
        }else if (lowerBound>upperBound){
            return -1;
        }else {
            if (list.get(curIn)<toFind){
                return recFind(list,toFind,curIn+1,upperBound);
            }else {
                return recFind(list,toFind,lowerBound,curIn-1);
            }
        }

    }
}
